/*
题目: 最大频率栈
设计一个类似堆栈的数据结构，将元素推入堆栈，并从堆栈中弹出出现频率最高的元素。
实现 FreqStack 类:

    FreqStack() 构造一个空的堆栈。
    void push(int val) 将一个整数 val 压入栈顶。
    int pop() 删除并返回堆栈中出现频率最高的元素。
        如果出现频率最高的元素不只一个，则移除并返回最接近栈顶的元素。

https://leetcode.cn/problems/maximum-frequency-stack
 */
class FreqStack {
    // 记录一个数出现的次数
    Map<Integer, Integer> freq = new HashMap<> ();
    // 记录出现 过(重点) 这个频率的 栈元素
    Map<Integer, Stack<Integer>> group = new HashMap<> ();
    // 定义一个变量, 记录最大频率, 方便删除最高频率的元素
    int maxFreq = 0;

    public FreqStack() {}
    
    public void push(int val) {
        int curFreq = freq.getOrDefault(val, 0) + 1;  // 这个元素的新次数
        freq.put(val, curFreq);
        maxFreq = Math.max(maxFreq, curFreq);   // 更新最大次数
        
        group.putIfAbsent(curFreq, new Stack<Integer> ());
        group.get(curFreq).push(val); // 这个频率, 新增元素
    }
    
    public int pop() {
        Stack<Integer> stk = group.get(maxFreq); // 弹出最大频率的元素
        int ret = stk.pop();
        freq.put(ret, freq.get(ret) - 1); // 拿出了这个元素, 这个元素次数 -1
        if (stk.isEmpty()) maxFreq -- ;   // 如果这个频率 没有元素了, 频率 减少

        return ret;
    }
}
